Infinite time Turing machine
Infinite time Turing machines (ITTMs) are a generalization of Turing machines to infinite computation lengths, first described by Joel David Hamkins and Andy Lewis.Infinite Time Turing Machines They lead to a stronger analog \(\Sigma_\infty\) to the busy beaver function. Definition The original model by Hamkins and Lewis has three one-side infinite tapes, called input, scratch ''and ''output tapes, and a single read-write head which reads one cell from each tape. (Models with one tape have been considered as well — surprisingly, they have been shown to be weaker.http://arxiv.org/abs/math/9907044) In addition to all the standard properties of ordinary TMs, ITTMs have a particular state marked as the limit state. At each step, the ITTM proceeds normally with a timer \(t\) starting at zero and incrementing at each step. If it does not halt for any \(t < \omega\), at \(t = \omega\) each cell on the tape is set to the of that cell's symbol for steps \(t = 0, 1, 2, \ldots\). In addition, the heads are set to the initial cell and the state is set to limit. The ITTM continues as before, and if it continues to \(t = \omega2\) without halting, the same thing happens with the limit superior of the tape for \(t = \omega, \omega + 1, \omega + 2, \ldots\). In general, if the ITTM reaches a countable limit ordinal \(\alpha\) without halting, at time \(t = \alpha\), it is set to the limit superior of the tape at \(t = \beta\) for all \(\beta < \alpha\) (i.e. it's set to 0 if, from some point below \(\alpha\) up to \(\alpha\) the cell is set to 0, and it's set to 1 otherwise). Formally, a two-color ITTM is a 5-tuple \(M = (Q, \delta, q_0, q_H, q_L)\) with the following components: * \(Q\) is a finite, non-empty set of states. * \(q_0 \in Q\) is the initial state. * \(q_H \in Q\) is the halting state. * \(q_L \in Q\) is the limit state. * \(\delta : (Q \backslash \{q_H\}) \times \{0, 1\}^3 \rightarrow Q \times \{0, 1\}^3 \times \{L, R\}\) is the transition table. A configuration of \(M\) is a 3-tuple \((p, \tau, m)\) where \(p \in (Q \backslash \{q_H\})\) is the current state of the machine, \(\tau : (\mathbb{N}\times\{0,1,2\}) \rightarrow \{0, 1\}\) are the contents of tapes, and \(m \in \mathbb{N}\) is the positions of the head. We use \(C(M)\) to denote the set of configurations. We define \(\leadsto\) (a single computation step) as a binary relation over \(C(M)\) as follows. We say that \((p, \tau, m) \leadsto (p', \tau', m')\) iff the following are true: * \(\delta(p, (\tau(m,0),\tau(m,1),\tau(m,2))) = (p', (c_0,c_1,c_2), \Delta m)\). * For all \(n \in \mathbb{N},i\in\{0,1,2\}\), \(\tau'(n,i) = \left\{ \begin{array}{lr} c_i & : n = m\\ \tau(n,i) & \text{otherwise} \end{array} \right.\). * \(m' = \left\{ \begin{array}{lr} m + 1 & : \Delta m = R \\ \max\{m - 1, 0\} & : \Delta m = L \end{array} \right.\) An input to an ITTM is simply a function \(I:\mathbb{N} \rightarrow \{0, 1\}\) (meant to be the content of the first tape), and an initial contents for that input is \(\tau_I:\mathbb{N}\times\{0,1,2\} \rightarrow \{0,1\}\) such that \(\tau_I(n,0)=I(n),\tau_I(n,1)=\tau_I(n,2)=0\). A computation of \(M\) on an input \(I\) is a function \(U : \mu \rightarrow C(M)\) (where \(\mu\) is a nonzero ordinal, or the class \(\text{On}\)) that satisfies the following properties: * \(U(0) = (q_0, \tau_I, 0)\) * For all \(\alpha < \mu\), \(U(\alpha) \leadsto U(\alpha + 1)\). * For all limit ordinals \(\alpha < \mu\), \(U(\alpha) = (q_L, \tau_\alpha, 0)\) where for all \(i \in \mathbb{N}\times\{0,1,2\}\), \(\tau_\alpha(i) = \text{lim sup} _{\beta < \alpha} \tau_\beta(i)\) where \(U(\beta) = (\bullet, \tau_\beta, \bullet)\).Bullets here indicate discarded portions of tuples. * If \(\mu \neq \text{On}\), \(U(\mu) = (q_H, \tau_\mu, \bullet)\). If \(\mu\neq\text{On}\), then \(\mu\) is called the halting time of the computation, and the function \(H:\mathbb{N} \rightarrow \{0,1\}\) defined as \(H(n)=\tau_H(n,2)\) is called the output of the computation. ITTM ordinals ITTMs are capable of producing far more outputs than ordinary TMs, including ordinals. This leads to several classes of ordinals: * An ordinal \(\alpha\) is writable iff an ITTM with trivial input can write \(\alpha\) and immediately halt. * An ordinal \(\alpha\) is clockable iff an ITTM with trivial input halts at time \(\alpha\). * An ordinal \(\alpha\) is eventually writable iff the output tape of an ITTM with trivial input ultimately converges to \(\alpha\). * An ordinal \(\alpha\) is accidentally writable iff an ITTM with trivial input writes \(\alpha\) at any step. (The first and last two definitions can apply to many mathematical objects other than ordinals) These definitions give rise to several large countable ordinals (the infinite time Turing machine ordinals): * \(\lambda\), the supremum of all writable ordinals * \(\gamma\), the supremum of all clockable ordinals * \(\zeta\), the supremum of all eventually writable ordinals * \(\Sigma\), the supremum of all accidentally writable ordinals It has been shown that \( \ll \lambda = \gamma < \zeta < \Sigma\)http://www.maths.bris.ac.uk/~mapdw/pdw4.ps. Encoding ordinals in bitstrings Here is a simple way to encode an ordinal in a countably infinite bitstring (read: output tape of a two-color ITTM): * "1000..." encodes \(0\). * If string S encodes \(\alpha\), then the string "0" + S (where + denotes string concatenation) encodes \(\alpha + 1\). * If strings \(S_0,S_1,S_2,\ldots\) encode \(\alpha_0,\alpha_1,\alpha_2,\ldots\), then we interleave the strings into a new bitstring \(T\) according to the following scheme: ** Start with every bit of \(T\) labeled "empty". ** Write the bits of \(S_0\) in every second bit of \(T\). ** Write the bits of \(S_1\) in every second remaining empty bit of \(T\). ** Write the bits of \(S_2\) in every second remaining empty bit of \(T\). ** Repeat for all of the \(S_i\). ** Write "1" in the first bit of \(T\). ** \(T\) encodes \(\sup\{\alpha_i\}\). This is of course one of many possible encoding schemes, and within this scheme multiple bitstrings represent a single ordinal. Klev's notations Ansten Mørch Klev developed two ordinal notations, \(\mathcal{O}^+\) and \(\mathcal{O}^{++}\), which express all writable and eventually writable ordinals, respectively. They are exactly the same as Kleene's \(\mathcal{O}\) but with analogous sets replacing the set of partial recursive functions. \(\Sigma_\infty\) Long and Stanleyhttp://arxiv.org/pdf/1401.2187v1.pdf propose an analog \(\Sigma_\infty\) of the busy beaver function. \(\Sigma_\infty(n)\) is defined as the maximal finite output \(k\) of an ITTM with at most \(n\) non-halting non-limit states given blank input, where they define output to be a natural number \(k\) if it is of the form \(\underbrace{11...1}_{k}00...\). They have shown that \(\Sigma_\infty\) eventually dominates every function \(\mathbb N\rightarrow\mathbb N\) which is computable by some ITTM, in analogy to domination property of \(\Sigma\) function. References See also ja:無限時間チューリングマシン Category:Transfinite ordinals Category:Unsolved problems